// 354. 俄罗斯套娃信封问题
// 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
// 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
// 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
// 注意：不允许旋转信封。
/**
 * @param {number[][]} envelopes
 * @return {number}
 */
var maxEnvelopes = function (envelopes) {
  const len = envelopes.length

  envelopes.sort((e1, e2) => {
    // 按照高度排序，高度相同则再按照宽度排序
    if (e1[0] !== e2[0]) {
      return e1[0] - e2[0]
    } else {
      return e2[1] - e1[1]
    }
  })

  // 第 i 个信封为最外层时，的最大信封个数
  const dp = new Array(len).fill(1)

  let ans = 1
  for (let i = 1; i < len; i++) {
    for (let j = 0; j < i; j++) {
      if (envelopes[j][1] < envelopes[i][1]) {
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
    }
    ans = Math.max(ans, dp[i])
  }

  return ans
}

// 提交没通过可以用二分法优化下
console.log(
  maxEnvelopes(
    [[46, 89], [50, 53], [52, 68], [72, 45], [77, 81]]
  )
)
